package leetcode_800;

import java.util.Arrays;

/**
 *@author 周杨
 *CherryPickup_741 一个人在二维数组里摘樱桃  往返两次 问最多摘多少樱桃
 *describe:用动态规划 AC 80%
 *2018年10月16日 上午10:43:45
 */
public class CherryPickup_741_ {

	/**
	 * describe:动态规划 用循环做 AC 11% 2018年10月16日 上午10:25:34
	 */
	public int cherryPickup(int[][] grid) {
		int n = grid.length;
		int[][][] dp = new int[n + 1][n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				Arrays.fill(dp[i][j], Integer.MIN_VALUE);
			}
		}
		dp[1][1][1] = grid[0][0];
		for (int x1 = 1; x1 <= n; x1++) {
			for (int y1 = 1; y1 <= n; y1++) {
				for (int x2 = 1; x2 <= n; x2++) {
					int y2 = x1 + y1 - x2;
					if (dp[x1][y1][x2] > 0 || y2 < 1 || y2 > n || grid[x1 - 1][y1 - 1] == -1
							|| grid[x2 - 1][y2 - 1] == -1) {
						continue;
						// have already detected || out of boundary || cannot access
					}
					int cur = Math.max(Math.max(dp[x1 - 1][y1][x2], dp[x1 - 1][y1][x2 - 1]),
							Math.max(dp[x1][y1 - 1][x2], dp[x1][y1 - 1][x2 - 1]));
					if (cur < 0) {
						continue;
					}
					dp[x1][y1][x2] = cur + grid[x1 - 1][y1 - 1];
					if (x1 != x2) {
						dp[x1][y1][x2] += grid[x2 - 1][y2 - 1];
					}
				}
			}
		}
		return dp[n][n][n] < 0 ? 0 : dp[n][n][n];
	}

	int[][][] dp;
	int[][] grid;

	/**
	 * describe:递归动态规划 AC 80%
	 * 2018年10月16日 上午11:10:04
	 */
	public int cherryPickup1(int[][] grid) {
		this.dp = new int[grid.length][grid.length][grid.length];
		this.grid = grid;
		for (int i = 0; i < grid.length; ++i)
			for (int j = 0; j < grid.length; ++j)
				for (int k = 0; k < grid.length; ++k)
					dp[i][j][k] = Integer.MIN_VALUE;
		return Math.max(0, help(grid.length - 1, grid.length - 1, grid.length - 1));
	}

	public int help(int x1, int y1, int x2) {
		int y2 = x1 + y1 - x2;
		if (x1 < 0 || y1 < 0 || x2 < 0 || y2 < 0)
			return -1;// 越界
		if (grid[x1][y1] == -1 || grid[x2][y2] == -1)
			return -1;// 走到刺上去了
		if (x1 == 0 && y1 == 0)
			return grid[x1][y1];// 结束了 那么另外一个也结束
		if (dp[x1][y1][x2] != Integer.MIN_VALUE)
			return dp[x1][y1][x2];
		int ans = Math.max(Math.max(help(x1 - 1, y1, x2 - 1), help(x1 - 1, y1, x2)),
				Math.max(help(x1, y1 - 1, x2), help(x1, y1 - 1, x2 - 1)));
		if (ans < 0)
			return dp[x1][y1][x2] = -1;// 该状态没有解
		ans += grid[x1][y1];
		if (x1 != x2)
			ans += grid[x2][y2];
		return dp[x1][y1][x2] = ans;
	}

}
